The problem of string searching occurs in many applications. The string search algorithm looks for a string called a “pattern” within a larger input string called the “text.” Multiple string searching refers to searching for multiple such patterns in the text string without having to search in multiple passes. In a string search, the text string is typically longer than several million bits long with the smallest unit being one octet in size. The start of a pattern string within the text is typically not known. A search method that can search for patterns when the start of patterns within the input string is not known in advance is known as unanchored searching. In an anchored search, the search algorithm is given the input string along with information on the offsets for start of the strings.
A network system attack (also referred to herein as an intrusion) is usually defined as an unauthorized or malicious use of a computer or computer network. In some cases, a network system attack may involve hundreds to thousands of unprotected network nodes in a coordinated attack, which is levied against specific or random targets. These attacks may include break-in attempts, including but not limited to, email viruses, corporate espionage, general destruction of data, and the hijacking of computers/servers to spread additional attacks. Even when a system cannot be directly broken into, denial of service attacks can be just as harmful to individuals and companies, who stake their reputations on providing reliable services over the Internet. Because of increasing usage and reliance upon network services, individuals and companies have become increasingly aware of the need to combat system attacks at every level of the network, from end hosts and network taps to edge and core routers.
Intrusion Detection Systems (or IDSs) are emerging as one of the most promising ways of providing protection to systems on a network. Intrusion detection systems automatically monitor network traffic in real-time, and can be used to alert network administrators to suspicious activity, keep logs to aid in forensics, and assist in the detection of new viruses and denial of service attacks. They can be found in end-user systems to monitor and protect against attacks from incoming traffic, or in network-tap devices that are inserted into key points of the network for diagnostic purposes. Intrusion detection systems may also be used in edge and core routers to protect the network infrastructure from distributed attacks.
Intrusion detection systems increase protection by identifying attacks with valid packet headers that pass through firewalls. Intrusion detection systems provide this capability by searching both packet headers and payloads (i.e., content) for known attack data sequences, referred to herein as “signatures,” and following prescribed actions in response to detecting a given signature. In general, the signatures and corresponding response actions supported by an intrusion detection system are referred to as a “rule-set database,” “IDS database” or simply “database.” Each rule in the database typically includes a specific set of information, such as the type of packet to search, a string of content to match (i.e., a signature), a location from which to start the search (e.g., for anchored searches), and an associated action to take if all conditions of the rule are matched. Different databases may include different sets of information, and therefore, may be tailored to particular network systems or types of attack.
At the heart of most modern intrusion detection systems is a string matching engine that compares the data arriving at the system to one or more signatures (e.g., strings or patterns) in the rule-set database and flags data containing an offending (e.g., matching) signature. As data is generally searched in real time in ever-faster network devices and rule databases continue to grow at a tremendous rate, string matching engines require rapidly increasing memory capacity and processing power to keep pace. Consequently, to avoid the escalating costs associated with ever-increasing hardware demands, designers have endeavored to improve the efficiency of the string matching methodology itself.
For example, FIG. 1A illustrates a goto-failure state graph or search tree embodying a signature definition including signatures K1-K4, where K1=“raining,” K2=“rains,” K3=“drains,” and K4=“nsdaq.” The state graph 100A includes a root node (S0) and nineteen elemental states 1-19 (hereinafter denoted as S1-S19) that form a search tree for the signatures K1-K4. Each of the nineteen states S1-S19 is reached from a previous state by a data-match or success transition that represents a corresponding character of the signatures K1-K4. In FIG. 1A, each success transition (which are sometimes referred to as goto transitions) is shown by a solid line extending from the previous state along with the edge “success” character value that enables the success transition to the next state (NS). Further, each of non-root states S1-S19 includes a “failure transition” to root node S0 that is taken if a current character (CC) of an input string does not match any success transitions originating at that state. For simplicity, only the failure transition 110 from state S1 to S0 is shown in FIG. 1A. However, it is to be understood that each of non-root states S1-S19 includes a failure transition to the root node S0. In addition, states S7, S13, S14, and S19 are designated as output states (and shown in bold to indicate such) because if any of those states is reached, at least one of the signatures has been matched by the input string, and an output code indicating the matching signature may be provided.
Each state in the search tree 100A can be viewed as representing a prefix of one or more of the signatures K1-K4. For example, state S3 represents a match between an input string and the prefix “rai” of signatures K1 and K2). Each of the states having two or more success transitions is referred to herein as a branch node, and each sequence of states subsequent to the branch node is referred to as a sub-branch. Thus, the strings that share a common prefix also share a corresponding set of parent states in the search tree. For example, search tree 100A includes three branches originating at root node S0. The first branch includes an initial state S1 and subsequent states S2-S7 and S14, where states S5-S7 form a first sub-branch at branch S4 that together with states S1-S4 represents K1=“raining,” and state S14 forms a second sub-branch at S4 that together with states S1-S4 represent K2=“rains.” The second branch includes an initial state S8 and subsequent states S9-S13 that represents K3=“damns.” The third branch includes an initial state S15 and subsequent states S16-S19 that represent K4=“nsdaq.” Further, the distance of a state from the root node in the goto graph is referred to as the depth of that state. For example, states S1, S8, and S15 have a depth of 1, states S2, S9, and S16 have a depth of 2, and so on.
For search trees such as goto graph 100A of FIG. 1A, a storage device typically stores state information for up to N*W nodes, where N is the number of signatures and W is the average length of a signature in bytes. The state information for each node typically includes the node's fail state, one or more success transitions and corresponding next states, and an output code.
During search operations between an input text string and the signatures K1-K4, a string search engine (not shown in FIG. 1A for simplicity) may use an input string cursor (C) to sequentially identify characters of the input string for comparison with the signature characters associated with success transitions from a current state (CS) of the search tree 100A. Further, a back pointer (BP) may be used to identify the first character of a potentially matching string within the input string.
For example, during a string search operation between an input string S1=“rains” and the signatures K1-K4 according to the search tree 100A of FIG. 1A, the cursor (C) and the back pointer (BP) are first initialized to zero so that both C and BP point to the first character “r” in the input string S1=“rains.” Also, the current state of the search engine is initialized to the root node S0 of the search tree. Then, a search engine operating according to the search tree 100A compares the current character (CC) identified by the cursor (e.g., C=0 and CC=“r”) with the success transitions originating at state S0. Because CC=“r” matches the “r” success transition 101 at S0, the search engine transitions from state S0 to S1 via the success transition 101. Next, the cursor is incremented by one position so that C=1 and CC=“a,” and the search engine compares CC=“a” with the success transitions originating at state S1. Because there is a match with the “a” success transition 102, the search engine transitions from S1 to S2 via the success transition 102. This process continues until the string search engine finally transitions from S4 to S14 via the “s” success transition upon a match with CC=“s” when C=4. State S14, which is an output state, outputs a match code indicating that the input string matches the signatures K2=“rains.” Note that upon the signature match with K2, the back pointer remains at BP=0 and thus identifies the “r” in the input string as the first character of the matching string. After the match condition is output, the search engine returns to the root node S0, the cursor and back pointer are incremented to the next character in the input string, thereby having traversed all the characters of the matching string “rains.”
When a failure transition is taken from a current state of the search tree 100A to the root node, the cursor is decremented (e.g., rewound) a number of positions in the input string equal to the number of states between the current state and the root node (e.g., the depth of the current state), minus one. For example, during a search operation between the input string S2=“rainy” and the signatures K1-K4 implemented according to search tree 100A, edge failure occurs at state S4 because the current character at S4, which is “y,” does not match either the “s” or the “i” success transition from state S4. Thus, at state S4, where C=4 and CC=“y,” the failure transition from S4 to the root node S0 (not shown for simplicity) is taken, and the cursor is rewound by 3 positions (e.g., from C=4 to C=1) to identify CC=“a” as the next input character to be examined, which requires characters “a,” “i,” and “n” of the input string to be re-processed by the search engine. Accordingly, because edge failure at any non-root state of search tree 100A requires returning to the root node S0 and rewinding the cursor according to the number of prior state transitions traversed into the tree (e.g., according to depth of the current state), string search operations implemented according to search tree 100A may require substantial reprocessing of data.
String search processing speeds may be improved by replacing some failure transitions to the root node S0 in search tree 100A with failure edges to non-root states. More specifically, the search tree 100A may be modified using the well-known Aho-Corasick (AC) scheme so that instead of returning to the root node upon edge failure, the search engine may transition to another non-root state that constitutes an accumulated prefix within the path in which edge failure occurs. For example, FIG. 1B shows a basic goto-failure state graph 100B that is created by adding non-root failure edges using the Aho-Corasick scheme, which are shown as dotted lines.
For one example, during string search operations performed according to the basic goto-failure graph 100B, if edge failure occurs at state S12 (e.g., because the cursor data is not an “s”), the search engine, having traversed the path “drain” in the second branch and thus already detected the prefix “rain” associated with the first branch, may transition directly from state S12 to S4 via failure edge 114 (e.g., without returning to the root node and then traversing through states S1-S4). Upon the failure transition 114 from S12 to S4, which corresponds to detection of the prefix “rain” of the signature K2=“rains,” the cursor remains constant at C=4 (e.g., to identify “n” as CC), and the back pointer is incremented by one position from BP=0 to BP=1 (e.g., to identify “r” as the first character in a potentially matching string). Thus, the matching pattern “rains” within the input string “drains” may be subsequently detected at state S14 without having to return to root node S0 upon edge failure at state S12. This is in contrast to the non-optimized search tree 100A, which upon edge failure from state S12 to the root node S0 would require rewinding the cursor by four positions and then require re-processing the first four characters “r,” “a,” “i,” and “n” of the input string. In this manner, transition to a non-root node in response to edge failure may save substantial data reprocessing and thus increase search speeds.
Note that search trees of the type shown in FIGS. 1A and 1B are commonly referred to as non-deterministic finite automaton because there can be more than one state transition on the same input character. For example, when an “i” input character is received at state S12 of the basic goto-failure search tree 100B, the failure transition 114 is first taken from S12 to S4, and then during another processing cycle, the “i” success transition is taken from S4 to S5.
It is known that a string search engine operating according to basic AC goto-failure state graphs such as search tree 100B of FIG. 1B typically have a worst-case processing speed of 0.5 characters per search cycle. More specifically, as described above, to complete a search operation between an input string and one or more signatures, the cursor and the back pointer must traverse over all the characters in the input string. Thus, for the goto-failure graph 100B of FIG. 1B, the cursor moves by one position on success transitions and remains constant on failure transitions, while the back pointer remains constant on success transitions and, in the worst-case scenario, increments by only one position on each failure transition. Accordingly, when searching an input string of Y characters using the goto-failure graph 100B of FIG. 1B, the search engine typically requires Y search cycles to traverse the cursor across the Y input characters and typically requires, in the worst-case scenario, Y additional search cycles to traverse the back pointer across the Y input characters, thereby resulting in a worst-case processing speed of Y characters/2Y cycles=0.5 character per search cycle.
Basic AC goto-failure state graphs that process one input character at a time, such as search tree 100B of FIG. 1B, may be further modified using AC techniques to achieve a worst-case processing speed that approaches 1 character per search cycle by adding enough cross edges (e.g., success transitions to states in other branches) to the state graph so that all failure transitions from non-root states may be eliminated. The resulting search tree is commonly known as a deterministic finite automaton (DFA) because exactly one state transition is made on each input character. More specifically, to eliminate all failure transitions in a goto-failure graph, a success transition for each possible path to a non-root state must exist for every state in the graph. For example, FIG. 1C shows a fully-expanded DFA search tree 100C created by expanding the basic goto-failure graph 100B of FIG. 1B to include an additional set of cross edges (also commonly referred to as next transitions) that allows for the elimination of all failure transitions. The newly added cross edges, which are illustrated as bold lines in FIG. 1C, collectively ensure that a failure transition is never taken from a non-root state, for example, so that the cursor is incremented on every state transition in the search tree. For example, if an input character “i” is received at state S12 of search tree 100C, the state machine transitions directly to S5 via the “i” cross edge from state S12 to S5 and increments the cursor to the next input character, thereby requiring only one state transition (and thus only one memory access) to process the input character “i.” In this manner, search operations performed according to the fully expanded state graph 100C of FIG. 1C typically process Y input characters in Y search cycles, thereby resulting in a worst-case processing speed of approximately 1 character per search cycle.
Although achieving nearly double the worst-case processing speed of search operations as the goto-failure state graph 100B of FIG. 1B, the fully-expanded AC DFA state graph of FIG. 1C requires significantly more memory area to store state information. For a simple example, while most of the states S1-S19 of search tree 100C of FIG. 1C include three success transitions, most of the states S1-S19 in state graph 100B of FIG. 1B include only one success transition, and therefore state graph 100C may require up to 3 times more storage area than state graph 100B. For actual implementations that involve hundreds of signatures, adding enough cross edges to the basic AC goto-failure search tree of the type depicted in FIG. 1B to create a fully-expanded AC search tree of the type depicted in FIG. 1C may increase the hardware storage requirements by two or more orders of magnitude. More specifically, for example, for a state graph that embodies hundreds of signatures each having an average length of between 60-70 ASCII-encoded characters (which uses an 8-bit encoding scheme to represent 256 different characters), which is common in today's security and search engine environments, it is likely that an average of 256 cross edges must be added to each state in the graph to eliminate all failure transitions, thereby requiring approximately 256 times more memory to store state information than basic goto-failure graphs of the type depicted in FIG. 1B.
As a result, for modern IDS applications in which a signature definition includes a large number of signatures, it is impractical to build a hardware implementation of a corresponding fully-expanded AC DFA search tree because of storage limitations of currently available memory devices. For example, to store state information for a fully-expanded state graph that embodies thousands of signatures each including dozens of characters, several million storage entries may be required, which is not feasible to implement using today's semiconductor storage devices.
Therefore, for modern string search operations, there is a need to dynamically balance processing speeds with storage area requirements to maximize the processing speeds achieved using a semiconductor storage device of a given size.
Like reference numerals refer to corresponding parts throughout the drawing figures.